/*
提交链接:https://leetcode.cn/problems/max-area-of-island/submissions/584591911/
695. 岛屿的最大面积
叶佳豪 2024/10/7
*/

class Solution {
public:
    int find(vector<int> &f, int x) {
        if (x != f[x]) {
            f[x] = find(f, f[x]);  
        }
        return f[x];
    }

    void unite(vector<int> &f, int x, int y) {
        int fx = find(f, x);
        int fy = find(f, y);
        if (fx != fy) {
            f[fy] = fx;
        }
    }

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        
        vector<int> f(row * col);
        vector<int> size(row * col, 0);

        // 初始化并查集
        for (int i = 0; i < row * col; ++i) {
            f[i] = i;
        }

        // 联合相邻的陆地
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (grid[i][j] == 1) {
                    int index = i * col + j;
                    // 加上边界判断
                    if (i - 1 >= 0 && grid[i - 1][j] == 1) unite(f, index, (i - 1) * col + j);
                    if (j - 1 >= 0 && grid[i][j - 1] == 1) unite(f, index, i * col + j - 1);
                    if (i + 1 < row && grid[i + 1][j] == 1) unite(f, index, (i + 1) * col + j);
                    if (j + 1 < col && grid[i][j + 1] == 1) unite(f, index, i * col + j + 1);
                }
            }
        }

        // 计算每个连通分量的大小
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (grid[i][j] == 1) {
                    int index = i * col + j;
                    int root = find(f, index);
                    size[root]++;
                }    
            }
        }

        // 找出最大的连通分量
        int maxArea = 0;
        for (int i = 0; i < row * col; ++i) {
            if (size[i] > maxArea) {
                maxArea = size[i];
            }
        }

        return maxArea;
    }
};